package person.bing.fbcloud.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: mengfanbing
 * @date: 2020/9/1 10:28
 */
public class Q30 {
    public static void main(String[] args) {
        String s = "barfoothefoobarman";
        String[] words = {"foo","bar"};
        List<Integer> substring = findSubstring(s, words);
        System.out.println(substring);
    }
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        if (s == null || s.isEmpty() || words == null || words.length == 0){
            return ans;
        }
        Arrays.sort(words);
        int sLength = s.length();
        int wordsLength = words.length;
        int wordLength = words[0].length();
        int allWordLength = wordsLength * wordLength;
        int startIndex = 0;
        int endIndex = startIndex + allWordLength - 1;
        while (sLength-1 >= endIndex){
            String[] subArray = new String[wordsLength];
            String substring = s.substring(startIndex, endIndex + 1);
            int j = 0;
            for (int i=0;i<wordsLength;i++){
                subArray[i] = substring.substring(j,j+wordLength);
                j=j+wordLength;
            }
            Arrays.sort(subArray);
            if (Arrays.equals(subArray,words)){
                ans.add(startIndex);
            }
            startIndex++;
            endIndex = startIndex + allWordLength - 1;
        }
        return ans;
    }
}
